#分治法的时间复杂度为 O(n log n)，因为每次递归将问题规模减半（log n 层），每层需要 O(n) 的时间处理跨越中间点的情况。
def max_subarray_divide_conquer(arr):
    def helper(low, high):
        # 基本情况：只有一个元素
        if low == high:
            return arr[low], (low, high)
        
        mid = (low + high) // 2
        
        # 递归求解左半部分和右半部分的最大子数组
        left_max, (left_low, left_high) = helper(low, mid)
        right_max, (right_low, right_high) = helper(mid + 1, high)
        
        # 计算跨越中间点的最大子数组
        cross_max, (cross_low, cross_high) = max_crossing_subarray(arr, low, mid, high)
        
        # 返回左、右、跨越中间点的最大值
        if left_max >= right_max and left_max >= cross_max:
            return left_max, (left_low, left_high)
        elif right_max >= left_max and right_max >= cross_max:
            return right_max, (right_low, right_high)
        else:
            return cross_max, (cross_low, cross_high)
    
    def max_crossing_subarray(arr, low, mid, high):
        # 向左扩展，找到包含arr[mid]的最大和
        left_sum = float('-inf')
        sum_temp = 0
        cross_low = mid
        for i in range(mid, low - 1, -1):
            sum_temp += arr[i]
            if sum_temp > left_sum:
                left_sum = sum_temp
                cross_low = i
        
        # 向右扩展，找到包含arr[mid+1]的最大和
        right_sum = float('-inf')
        sum_temp = 0
        cross_high = mid + 1
        for j in range(mid + 1, high + 1):
            sum_temp += arr[j]
            if sum_temp > right_sum:
                right_sum = sum_temp
                cross_high = j
        
        # 返回跨越中间点的最大和及其区间
        return left_sum + right_sum, (cross_low, cross_high)
    
    max_sum, (i, j) = helper(0, len(arr) - 1)
    return max_sum, (i, j)

# 示例：使用10个数的实数序列
arr = [1, -2, 3, 10, -4, 7, 2, -5, -8, 6]
max_sum, (i, j) = max_subarray_divide_conquer(arr)

print("序列:", arr)
print("最大子数组和:", max_sum)
print("最大子数组的区间: 从索引", i, "到", j)
print("最大子数组:", arr[i:j+1])
